package com.datastructure.test.findtargetfromrotatearray;

import java.util.Arrays;

public class FindTargetFromRotateArray {

    public static void main(String[] args) {
        int[] data = {6,8,10,0,2,4};
        FindTargetFromRotateArray findTargetFromRotateArray = new FindTargetFromRotateArray();
        int search = findTargetFromRotateArray.search(data, 4);
        System.out.println(search);
    }

    public int search (int[] nums, int target) {
        // write code here
        int index=0;
        for (int i = 0; i < nums.length; i++) {
            if(i>0&&nums[i]<nums[i-1]){
                index=i;
            }
        }
        int binarySearch = binarySearch(nums, 0, index - 1, target);
        if(binarySearch!=-1){
            return binarySearch;
        } else {
            return binarySearch(nums,index, nums.length-1, target);
        }
    }
    public int binarySearch(int[] arr, int left, int right, int findVal){
        // 当left > right 时，说明递归整个数组，但是没有找到
        if(left > right){
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if(findVal > midVal){ // 向右递归
            return binarySearch(arr, mid + 1,right,findVal);
        } else if (findVal < midVal){
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
}
